#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    node->_data = x;
    node->_left = NULL;
    node->_right = NULL;

    return node;
}
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);

    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;

    return node1;
}
void preOrder(BTNode * root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->_data);
    preOrder(root->_left);
    preOrder(root->_right);

}

void inOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    inOrder(root->_left);
    printf("%d ", root->_data);
    inOrder(root->_right);
}


void postOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    postOrder(root->_left);
    postOrder(root->_right);
    printf("%d ", root->_data);
}

int TreeSize(BTNode* root)
{
    return root == NULL ? 0 :
        TreeSize(root->_left)
        + TreeSize(root->_right)
        + 1;
}

int TreeHeight(BTNode* root)
{
    if (root == NULL)
        return 0;

    int leftHeight = TreeHeight(root->_left);
    int rightHeight = TreeHeight(root->_right);

    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int TreeKLevel(BTNode* root, int k)
{
    assert(k > 0);

    if (root == NULL)
        return 0;

    if (k == 1)
        return 1;

    return TreeKLevel(root->_left, k - 1)
        + TreeKLevel(root->_right, k - 1);
}
int main()
{
    BTNode* root = CreatBinaryTree();
    preOrder(root);
    printf("\n");

    inOrder(root);
    printf("\n");

    postOrder(root);
    printf("\n");
    

    printf("TreeSize:%d\n", TreeSize(root));
    printf("TreeSize:%d\n", TreeSize(root));
    printf("TreeSize:%d\n", TreeSize(root));
    printf("TreeHeight:%d\n", TreeHeight(root));
    printf("TreeKLevel:%d\n", TreeKLevel(root, 3));
    printf("TreeKLevel:%d\n", TreeKLevel(root, 4));

    return 0;
}